package com.zwj.interview.数组;


import java.util.HashMap;
import java.util.Map;

/**
 * 输入一个整数数组和一个整数k，请问数组中有多少个数字之和等于k的连续子数组？
 * 例如，输入数组[1，1，1]，k的值为2，有2个连续子数组之和等于2
 */
public class SumEqualKSubArrayCount前缀和 {


    /**
     * 在从头到尾逐个扫描数组中的数字时求出前i个数字之和，并且将和保存下来。
     * 数组的前i个数字之和记为x。如果存在一个j（j>i），数组的前j个数字之和为x-k，
     * 那么数组中从第i+1个数字开始到第j个数字结束的子数组之和为k
     *
     * @param nums
     * @param k
     * @return 这个题目需要计算和为k的子数组的个数。当扫描到数组的第i个数字并求得前i个数字之和是x时，
     * 需要知道在i之前存在多少个j并且前j个数字之和等于x-k。所以，对每个i，不但要保存前i个数字之和，
     * 还要保存每个和出现的次数。分析到这里就会知道我们需要一个哈希表，哈希表的键是前i个数字之和，值为每个和出现的次数
     */
    public static int subArraySum(int[] nums, int k) {
        //保存前缀和到出现次数的映射关系
        Map<Integer, Integer> sumToCount = new HashMap<>();
        sumToCount.put(0, 1);
        //sum为前缀和
        int sum_i = 0;
        int count = 0;
        for(int i=0;i<nums.length;i++){
            sum_i+=nums[i];
            //sum_j为前缀和nums[0..j]
            int sum_j=sum_i-k;
            if(sumToCount.containsKey(sum_j)){
                count+=sumToCount.get(sum_j);
            }
            //把前缀和nums[0..i]加入并记录出现次数
            sumToCount.put(sum_i,sumToCount.getOrDefault(sum_i,0)+1);
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(subArraySum(new int[]{1,1,1},2));
    }


    //前缀和
   class PrefixSum{
       // 前缀和数组
       private int[] prefix;

       /* 输入一个数组，构造前缀和 */
       public PrefixSum(int[] nums) {
           prefix = new int[nums.length + 1];
           // 计算 nums 的累加和
           for (int i = 1; i < prefix.length; i++) {
               prefix[i] = prefix[i - 1] + nums[i - 1];
           }
       }

       /* 查询闭区间 [i, j] 的累加和 */
       public int query(int i, int j) {
           return prefix[j + 1] - prefix[i];
       }
   }


}
